import heapq
class Solution(object):
    def getCollisionTimes(self, cars):
        n = len(cars)
        ans = [-1] * n
        st = []
        for i in range(n - 1):
            if cars[i + 1][1] < cars[i][1]:
                st.append([(cars[i + 1][0] - cars[i][0]) / (cars[i][1] - cars[i + 1][1]), i, i + 1])
        heapq.heapify(st)

        p = [i for i in range(n)]
        def find(x):
            if p[x] == x:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        while st:
            time, i, j = heapq.heappop(st)
            if ans[j] == -1:
                ans[i] = time
                p[j] = i
                last_i = find(i) - 1
                if last_i >= 0:
                    if cars[j][1] < cars[last_i][1]:
                        heapq.heappush(st, [(cars[j][0] - cars[last_i][0]) / (cars[last_i][1] - cars[j][1]), last_i, j])
        return ans      
                
# O(n)单调栈
class Solution(object):
    def getCollisionTimes(self, cars):
        n = len(cars)
        st = []
        ans = [-1] * n
        for i in range(n - 1, -1, -1):
            pos, speed = cars[i]
            while st and speed <= st[-1][1]:
                st.pop()
            while st:
                j = len(st) - 1
                time  = (st[j][0] - pos) / (speed - st[j][1])
                if j > 0 and time < (st[j - 1][0] - st[j][0]) / (st[j][1] - st[j - 1][1]) or j == 0:
                    ans[i] = time
                    break
                else:
                    st.pop()
            st.append([pos, speed])
        return ans



data = Solution()
cars = [[1,2],[2,1],[4,3],[7,2]]
print(data.getCollisionTimes(cars))
cars = [[3,4],[5,4],[6,3],[9,1]]
print(data.getCollisionTimes(cars))